package microsoft;

import java.util.ArrayList;
import java.util.List;

public class Test1 {

    public static void main(String[] args) {
        System.out.println(new Test1().solution("...xxx..x....xxx.", 7));
    }

    /**
     * 字符串s中的x代表坑洞
     * 修复连续k个坑洞时费用为k+1
     * 能连续修优先连续修
     * @param S 带有坑洞的字符串
     * @param B 预算
     * @return 修理的最长坑洞数量
     */
    public int solution(String S, int B){
        if (B <= 1) return 0;
        int cur = 0;
        List<Integer> list = new ArrayList<>();
        for (char c : S.toCharArray()){
            if (c == 'x'){
                cur++;
            }else if (cur != 0){
                list.add(cur);
                cur = 0;
            }
        }
        if (cur != 0) list.add(cur);
        if (list.size() == 0) return 0;
        list.sort((a, b) -> b - a);
        int res = 0;
        for (int n : list){
            if (B < 2) break;
            if (B >= n + 1){
                res += n;
                B -= n + 1;
            }else {
                res += B - 1;
                B = 0;
            }
        }
        return res;
    }
}











